home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 7 / BBS in a Box - Macintosh - Volume VII (BBS in a Box) (January 1993).iso / Files / Prog / M / Mac gperf 1.9.cpt / Mac gperf 1.9 / src / listnode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-03-09  |  5.0 KB  |  138 lines  |  [TEXT/KAHL]
  1. /* Creates and initializes a new list node.
  2.    Copyright (C) 1989 Free Software Foundation, Inc.
  3.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  4.  
  5. This file is part of GNU GPERF.
  6.  
  7. GNU GPERF is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 1, or (at your option)
  10. any later version.
  11.  
  12. GNU GPERF is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with GNU GPERF; see the file COPYING.  If not, write to
  19. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. #include <stdio.h>
  22.  
  23. #include "options.h"
  24. #include "stderr.h"
  25. #include "xmalloc.h"
  26.  
  27. #include "listnode.h"
  28.  
  29. /* See comments in perfect.cc. */
  30. extern int occurrences[ALPHABET_SIZE]; 
  31.  
  32. /*******************************************************************************\
  33. *                              Prototypes                                        *
  34. \*******************************************************************************/
  35.  
  36. static void        set_sort( char * base, int len );
  37.  
  38.     /***********************************************************************\
  39.     *                                                                        *
  40.     * name:        set_sort                                                    *
  41.     *                                                                        *
  42.     * descr:    Sorts the key set alphabetically to speed up subsequent     *
  43.     *            operations. Use insertion sort since the set is probably    *
  44.     *            very small.                                                    *
  45.     *                                                                        *
  46.     \***********************************************************************/
  47.  
  48. static void set_sort( char * base, int len )
  49. {
  50.   int i, j;
  51.  
  52.   for (i = 0, j = len - 1; i < j; i++)
  53.     {
  54.       char curr, tmp;
  55.       
  56.       for (curr = i + 1, tmp = base[curr]; curr > 0 && tmp < base[curr-1]; curr--)
  57.         base[curr] = base[curr - 1];
  58.  
  59.       base[curr] = tmp;
  60.  
  61.     }
  62. }
  63.  
  64.     /***********************************************************************\
  65.     *                                                                        *
  66.     * name:        make_list_node                                                *
  67.     *                                                                        *
  68.     * descr:    Initialize a list_node.                                        *
  69.     *                                                                        *
  70.     \***********************************************************************/
  71.  
  72. /* Initializes a List_Node.  This requires obtaining memory for the KEY_SET
  73.    and UNIQ_SET, initializing them using the information stored in the
  74.    KEY_POSITIONS array in Options, and checking for simple errors.
  75.    It's important to note that KEY and REST are both pointers to
  76.    the different offsets into the same block of dynamic memory pointed to
  77.    by parameter K. The data member REST is used to store any additional fields 
  78.    of the input file (it is set to the "" string if Option[TYPE] is not enabled).
  79.    This is useful if the user wishes to incorporate a lookup structure,
  80.    rather than just an array of keys. */
  81.  
  82. LIST_NODE * make_list_node( char * k, int len )
  83. {
  84.   LIST_NODE *temp = (LIST_NODE *) xmalloc (sizeof (LIST_NODE));
  85.   int positions  = 1 + (OPTION_ENABLED (option, ALLCHARS) ? len : TOTAL_POSITIONS (option) + 1);
  86.   char *ptr, *ptr1, *ptr2;
  87.  
  88.   temp->key_set  = (char *) xmalloc (positions + positions); /* Save 1 call to new. */
  89.   temp->uniq_set = temp->key_set + positions;
  90.   ptr            = temp->key_set;
  91.   k[len]         = '\0';        /* Null terminate KEY to separate it from REST. */
  92.   temp->key      = k;
  93.   temp->next     = 0;
  94.   temp->index    = 0;
  95.   temp->length   = len;
  96.   temp->link     = 0;
  97.   temp->rest     = OPTION_ENABLED (option, TYPE) ? k + len + 1 : "";
  98.  
  99.   if (OPTION_ENABLED (option, ALLCHARS)) /* Use all the character position in the KEY. */
  100.  
  101.     for (; *k; k++, ptr++)
  102.       ++occurrences[*ptr = *k];
  103.  
  104.   else                          /* Only use those character positions specified by the user. */
  105.     {                           
  106.       int i;
  107.  
  108.       /* Iterate thru the list of key_positions, initializing occurrences table
  109.          and temp->key_set (via char * pointer ptr). */
  110.  
  111.       for(RESET (option); (i = GET (option)) != EOS; )
  112.         {
  113.           if (i == WORD_END)    /* Special notation for last KEY position, i.e. '$'. */
  114.             *ptr = temp->key[len - 1];
  115.           else if (i <= len)    /* Within range of KEY length, so we'll keep it. */
  116.             *ptr = temp->key[i - 1];
  117.           else                  /* Out of range of KEY length, so we'll just skip it. */
  118.             continue;
  119.           ++occurrences[*ptr++];
  120.         }
  121.  
  122.       if (ptr == temp->key_set) /* Didn't get any hits, i.e., no usable positions. */
  123.         report_error ("can't hash keyword %s with chosen key positions\n%a", temp->key);
  124.     }
  125.  
  126.   *ptr = '\0';                  /* Terminate this bastard.... */
  127.   set_sort (temp->key_set, ptr - temp->key_set); /* Sort the KEY_SET items alphabetically. */
  128.  
  129.   /* Eliminate UNIQ_SET duplicates, this saves time later on.... */
  130.  
  131.   for (ptr1 = temp->key_set, ptr2 = temp->uniq_set; *ptr1; ptr1++)
  132.     if (*ptr1 != ptr1[1])
  133.       *ptr2++ = *ptr1;
  134.  
  135.   *ptr2 = '\0';                 /* NULL terminate the UNIQ_SET. */
  136.   return temp;
  137. }
  138.